//有效的括号
/*给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。*/
class Solution {
public:
    bool isValid(string s) {
        string st;
        for (char& c : s) {
            if (c == '(' || c == '{' || c == '[') {
                st.push_back(c);
            } else {
                if (st.empty())
                    return false;
                if (c == ')' && st.back() == '(') {
                    st.pop_back();
                } else if (c == '}' && st.back() == '{') {
                    st.pop_back();

                } else if (c == ']' && st.back() == '[') {
                    st.pop_back();
                } else
                    return false;
            }
        }
        if (st.size())
            return false;
        return true;
    }
};


//用队列实现栈
/*请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。*/
class Solution {
public:
    bool isValid(string s) {
        string st;
        for (char& c : s) {
            if (c == '(' || c == '{' || c == '[') {
                st.push_back(c);
            } else {
                if (st.empty())
                    return false;
                if (c == ')' && st.back() == '(') {
                    st.pop_back();
                } else if (c == '}' && st.back() == '{') {
                    st.pop_back();

                } else if (c == ']' && st.back() == '[') {
                    st.pop_back();
                } else
                    return false;
            }
        }
        if (st.size())
            return false;
        return true;
    }
};